#include <iostream>
using namespace std;

#define    MAX    100
#define    INF    999999999
int N;//任务交接点数量
int M;//子任务数量

int G[MAX][MAX];//定义表

//定义点结构体
typedef struct
{
    int earlytime;//事件发生的最早时间
    int lasttime;//事件发生的最晚时间
    int indegree;
    int outdegree;
}Point;

Point point[MAX];

//先将表初始化一下
void InitGraph()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            G[i][j] = 0;
        }
    }
}

void InitPoint()
{
    for (int i = 1; i <= N; i++)
    {
        point[i].earlytime = 0;
        point[i].lasttime = INF;
        point[i].indegree = 0;
        point[i].outdegree = 0;
    }
}

//读入数据M行
void InsertG()
{
    int x, y, time;//从x->y用时time
    for (int i = 1; i <= M; i++)
    {
        scanf("%d %d %d", &x, &y, &time);
        G[x][y] = time;
        point[x].outdegree++;//x是起点
        point[y].indegree++;//y是终点
    }
}

//最早时间
int Earlytime()
{
    int Queue[MAX];
    int top = 0, rear = 0;
    int maxtime = 0;
    for (int i = 1; i <= N; i++)
    {
        if (point[i].indegree == 0)//入度为0的点入队列
        {
            point[i].indegree--;
            Queue[++top] = i;
        }
    }

    int points;
    while (top != rear)
    {
        points = Queue[++rear];//出队列
        for (int i = 1; i <= N; i++)
        {
            if (G[points][i])//从0到i有路径
            {
                point[i].indegree--;//i的入度减一
                if (point[i].indegree == 0)//入度为0再进队列
                {
                    Queue[++top] = i;
                }
                if (point[i].earlytime < point[points].earlytime + G[points][i])//i的最早发生时间小于
                {
                    point[i].earlytime = point[points].earlytime + G[points][i];//替换
                    if (point[i].earlytime > maxtime)//最大时间
                    {
                        maxtime = point[i].earlytime;
                    }
                }
            }
        }
    }

    if (top != N)
    {
        return 0;
    }

    return maxtime;
}


void Lasttime(int time)
{
    int Queue[MAX];
    int top = 0, rear = 0;
    for (int i = 1; i <= N; i++)
    {
        if (point[i].outdegree == 0)//起点为0的点入队列
        {
            Queue[++top] = i;
            point[i].lasttime = time;
            point[i].outdegree--;
        }
    }

    int points = 0;
    while (top != rear)
    {
        points = Queue[++rear];//出队
        for (int i = 1; i <= N; i++)
        {
            if (G[i][points])//i与该点之间有路径
            {
                point[i].outdegree--;//起点减一
                if (point[i].outdegree == 0)//等于0再入队列
                {
                    Queue[++top] = i;
                }
                if (point[points].lasttime - G[i][points] < point[i].lasttime)//替换前一个节点的时间
                {
                    point[i].lasttime = point[points].lasttime - G[i][points];
                }
            }
        }
    }

    for (int i = 1; i <= N; i++)
    {
        if (point[i].lasttime == point[i].earlytime)
        {
            for (int j = N; j >= 1; j--)
            {
                if (G[i][j] != 0 && point[j].lasttime == point[j].earlytime && point[i].lasttime == point[j].lasttime - G[i][j])
                {
                    printf("%d->%d\n", i, j);
                }
            }
        }
    }
}


int main()
{
    cin>>N>>M;
    InitGraph();
    InitPoint();
    InsertG();
    int time = 0;
    time = Earlytime();
    if (time == 0)
    {
        cout<<"0";
    }
    else
    {
        cout<<time<<endl;
        Lasttime(time);
    }


    return 0;
}

